class BitTree:
    def __init__(self, val):
        self.val = val
        self.lchild = None
        self.rchild = None
        self.parent = None


class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for ii in li:
                self.insert_sec(ii)
    

    def insert_sec(self, val):
        p = self.root
        if not p:
            self.root = BitTree(val)
        
        while True:
            if val > p.val:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BitTree(val)
                    p.rchild.parent = p
                    return
            elif val < p.val:
                if not p.lchild:
                    p = p.lchild
                else:
                    p.lchild = BitTree(val)
                    p.lchild.parent = p
                    return
            else:
                return
            
    
    def insert(self, node, val):
        if not node:
            node = BitTree(val)
            return node
        
        if val > node.val:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        elif val < node.val:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        return node
    
    def query_no(self, val):
        p = self.root
        if not p:
            return None
        
        while p:
            if val > p.val:
                p = p.rchild
            
            elif val < p.val:
                p = p.lchild
            
            else:
                return p
        return None
    
    def query(self, node, val):
        if not node:
            return None
        if val > node.val:
            return self.query(node.rchild, val)
        elif val < node.val:
            return self.query(node.lchild, val)
        else:
            return node
        
    
    def __remove_node_1(self, node):
        if not node.parent:
            self.root = None

        if node == node.parent.lchild:
            node.parent.lchild = None
        else:
            node.parent.rchild = None

    def __remove_node_21(self,node):
        # 只有一个左孩子
        if not node.parent:
            self.root = node.lchild
            node.lchild.parent = None
        
        if node == node.parent.lchild:
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent

        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
    
    def __remove_node_22(self, node):
        if not node.parent:
            self.root = node.rchild
            node.rchild.parent = None
        
        if node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent


    def delete(self, val):
        if self.root:
            node = self.query_no(val)
            if not node:
                return False
            elif not node.lchild and not node.rchild:
                self.__remove_node_1(node)
            elif not node.rchild:
                self.__remove_node_21(node)
            elif not node.lchild:
                self.__remove_node_22(node)
            else:
                min_node = node.rchild
                while min_node.lchild:
                    min_node = min_node.lchild
                node.val = min_node.val
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)
                